/**
 * 判断无向图是否是一棵树--->判断一棵树是否没有环
 * --->图G必须是无回路的连通图，或者图G中有m-1条边。
 * 对于连通的判定，可以采用DFS在遍历图的过程中统计可能访问到的顶点数和边G一定是数
 * 若一次遍历就能访问到n个顶点和n-1条边，则判断该图一颗树!
 */
bool isTree(Graph* G)
{
	//初始化visited数组
	for(int i=0; i<G->vertex_num; i++)
	{
		visited[i]=false;
	}
	
	int vex_count=0, edge_count=0;	//顶点数和边数累加器
	//从顶点1开始遍历
	DFS(G, 1, vex_count, edge_count,visited);
	//边数=n-1 且顶点数相等
	if(vex_count==G->vex_num && edge_count==2*(G->vex_num-1))
		return true;
	else return false;
}

void DFS(Graph* G, int v, int& vex_count, int& edge_count, int visited[])
{
	//从顶点v开始遍历
	visited[v]=true;
	//w为第一个相邻的顶点
	int w=FirstNeighbor(G, v);
	while(w!=-1)	//找到了该顶点w(存在)
	{
		edge_count++;	//存在这条边，故边数累加器+1
		if(!visited[w]) //如果该w顶点没有被访问过，则继续寻找与它的下一个顶点
		{
			DFS(G, w, vex_count,edge_count, visited);
		}
		w=NextNeighbor(G,v,w);	//	如果该顶点w已经被访问过了，则继续寻找除了w顶点以外其它下一个顶点
	}
}